package leetcode

import "math"

/*
 * @lc app=leetcode.cn id=85 lang=golang
 *
 * [85] 最大矩形
 */

// @lc code=start
func maximalRectangle(matrix [][]byte) int {
	n, m := len(matrix), len(matrix[0])
	if n == 0 || m == 0 {
		return 0
	}

	left := make([][]int, m)
	for i, row := range matrix {
		left[i] = make([]int, n)
		for j, v := range row {
			if v != '0' {
				if j == 0 {
					left[j][i] = 1
				} else {
					left[j][i] = left[j-1][i] + 1
				}
			}
		}
	}
	area := 0.0
	for _, col := range left {
		area = math.Max(area, float64(largestRectangleArea(col)))
	}

	return int(area)
}

// @lc code=end
